
#include <iostream>
#include <vector>
#include <unordered_set>

class Solution 
{
public:
    int alltrue = 0, n = 0;
    vector<vector<bool>> vis;

    int citys(vector<vector<int>>& m)
    {
        int res = 0;
        n = m.size();
        vis.resize(n, vector<bool>(n, false));
        unordered_set<int> begcity;

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (m[i][j] && !vis[i][j])
                {
                    vis[i][j] = true;
                    ++alltrue;

                    if (!begcity.count(i))
                        begcity.insert(i);

                    vector<int> secondcity(j);
                    AllSecondCity(m, secondcity, 0);
                    ++res;

                    if (alltrue == n * n)
                        break;
                }
            }
            if (alltrue == n * n)
                break;
        }

        return res;
    }
private:
    void AllSecondCity(vector<vector<int>>& m, vector<int>& v, int idx)
    {
        while (idx < v.size())
        {
            int i = v[idx++];
            for (int j = 0; j < n; ++j)
            {
                if (m[i][j] && !vis[i][j])
                {
                    v.push_back(j);
                    vis[i][j] = true;
                    ++alltrue;
                }
            }
        }
    }
};

void Test1()
{
    vector<vector<int>> m({ {1, 1, 0},{1, 1, 0},{0, 0, 1 }});
}

int main()
{
    Test1();

    return 0;
}